import java.util.LinkedList;
import java.util.List;
import java.util.Stack;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
    }
}
class Solution {

    /**
     * 145二叉树的后续遍历
     * https://leetcode.cn/problems/binary-tree-postorder-traversal/
     */
    List<Integer> list = new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null) return list;

        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);
        return list;
    }

    /**
     * 144二叉树的前序遍历
     * https://leetcode.cn/problems/binary-tree-preorder-traversal/
     */
    List<Integer> list1 = new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) {
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }

    /**
     * 94二叉树的中序遍历
     * https://leetcode.cn/problems/binary-tree-inorder-traversal/
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        inorder(root, list);
        return list;
    }
    public void inorder(TreeNode root, List<Integer> list) {
        if(root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
    public List<Integer> inorderTraversal2(TreeNode root) {
        //非递归
        List<Integer> list = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();

        while(root != null || !stack.empty()) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }

    /**
     * 14最长公共前缀
     * https://leetcode.cn/problems/longest-common-prefix/description/
     * @param strs
     * @return
     */

    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0) {
            return null;
        }
        char c;
        for(int i = 0; i < strs[0].length(); i++) {
            c = strs[0].charAt(i);
            //纵向比较
            for(int j = 1; j < strs.length; j++) {
                if(strs[j].length() == i || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}